"""
Project Euler Problem 9: https://projecteuler.net/problem=9

Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

    a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product a*b*c.
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.7.3
@creat_time = 2022/5/6
'''


def solution(n: int = 1000) -> list:
    '''
    (1). a^2 + b^2 = c^2   
    (2). a + b + c = n         
    (3). a < b < c         
    
    from (1)(2),
        ==> (4). a+b = ab/n + n/2
        ==> (5). n must be an even number, and ab % n == 0
    
    from (3)(4),
        3a < a+b+c = n 
        ==> (6). a < n/3
        2b < a+b+c = n
        ==> (7). b < n/2
        2b > a+b = ab/n + n/2 > a^2/n + n/2  
        ==> (8). b > a^2/(2n) + n/4
    
    >>> assert solution(12) == [(3, 4, 5)]
    >>> assert solution() == [(200, 375, 425)]
    '''
    
    if n % 2 != 0:  # (5)
        return []
    
    n_half = n>>1 
    
    res = []
    
    for a in range(1,n//3 + 1):  # (6)
        b_min = max(a+1, int(n/4 + a**2/(n<<1)))  # (3)(8)

        for b in range(b_min, n_half ):  # (7) 
            m, k = divmod(a*b, n) 
            if k == 0:  # (5)
                if m == a + b - n_half:  # (4)
                    res.append((a, b, n-a-b))
                
    return res

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    
    print(f"solution() = {solution()}")


    


